// 基本思想：按照一定间隔划分为若干子序列，每个子序列分别进行插入排序，然后逐渐缩小间隔进行下一轮划分子序列和对子序列
// 进行插入排序，直至最后一轮间隔为1，对整个序列进行插入排序

// 步骤：1. 确定元素间隔数gap，2.将序列按照间隔数分成若干子序列， 3. 对子序列采用某种排序算法排序，
// 4. 减少间隔数，重新划分若干子序列，再分别对各个子序列进行排序，以此类推直到gap = 1，排序结束

// 时间复杂度：介于O(nlogn)与O(n^2)之间
// 排序稳定性：不稳定
function shellSort(arr) {
    let size = arr.length
    let gap = Math.floor(size / 2)
    while (gap > 0) {
        for (let i = 0; i < size; i++) {
            let temp = arr[i]        
            let j = i
            // 从右到左遍历每组中的有序序列元素
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap = Math.floor(gap / 2)
    }
    return arr
}
let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(shellSort(arr))